// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// N.B. The offline symbolizer (scripts/symbolize) reads our output,
// don't break it.

#include <inttypes.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <backtrace/backtrace.h>

#include <ngunwind/libunwind.h>
#include <ngunwind/fuchsia.h>

#include <zircon/types.h>
#include <zircon/syscalls.h>
#include <zircon/syscalls/object.h>

#include <fbl/alloc_checker.h>
#include <fbl/array.h>

#include "inspector/inspector.h"
#include "dso-list-impl.h"
#include "utils-impl.h"

namespace inspector {

// Keep open debug info for this many files.
constexpr size_t kDebugInfoCacheNumWays = 2;

constexpr unsigned int kBacktraceFrameLimit = 50;

// Error callback for libbacktrace.

static void bt_error_callback(void* vdata, const char* msg, int errnum) {
  fprintf(stderr, "%s", msg);
  if (errnum > 0)
    fprintf(stderr, ": %s", strerror(errnum));
  fprintf(stderr, "\n");
}

// backtrace_so_iterator function.
// We don't use libbacktrace to do the unwinding, we only use it to get
// file,line#,function_name for each pc. Therefore we don't need it to
// iterate over all shared libs.

static int bt_so_iterator(void* iter_state, backtrace_so_callback* callback, void* data) {
  // Return non-zero so iteration stops.
  return 1;
}

// A cache of data stored for each shared lib.
// This lets us lazily obtain debug info, and only keep
// a subset of it in memory.
class DebugInfoCache {
 public:
  DebugInfoCache(inspector_dsoinfo_t* dso_list, size_t nr_ways);
  ~DebugInfoCache();

  inspector_dsoinfo_t* dso_list() { return dso_list_; }

  zx_status_t GetDebugInfo(uintptr_t pc, inspector_dsoinfo_t** out_dso,
                           backtrace_state** out_bt_state);

 private:
  inspector_dsoinfo_t* dso_list_;

  size_t last_used_ = 0;

  bool cache_avail_ = false;

  struct way {
    // Not owned by us. This is the "tag".
    inspector_dsoinfo_t* dso = nullptr;
    // Owned by us.
    backtrace_state* bt_state = nullptr;
  };

  fbl::Array<way> ways_;
};

// Note: We *do not* take ownership of |dso_list|.
// Its lifetime must survive ours.

DebugInfoCache::DebugInfoCache(inspector_dsoinfo_t* dso_list, size_t nr_ways)
    : dso_list_(dso_list) {
  fbl::AllocChecker ac;
  auto ways = new (&ac) way[nr_ways];
  if (!ac.check()) {
    debugf(1, "unable to initialize debug info cache\n");
    return;
  }
  ways_.reset(ways, nr_ways);
  cache_avail_ = true;
}

DebugInfoCache::~DebugInfoCache() {
  if (cache_avail_) {
    for (size_t i = 0; i < ways_.size(); ++i) {
      backtrace_destroy_state(ways_[i].bt_state, bt_error_callback, nullptr);
    }
  }
}

// Find the DSO and debug info (backtrace_state) for PC.
// Returns ZX_ERR_NOT_FOUND if |pc| is not in any DSO.
// Otherwise the result is ZX_OK, even if there is no extended debug
// info for libbacktrace (e.g., -g1 info).
// If the result is ZX_OK then |*out_dso| is set.
// If the result is ZX_OK then |*out_bt_state| is set to the
// accompanying libbacktrace state if available or nullptr if not.

zx_status_t DebugInfoCache::GetDebugInfo(uintptr_t pc, inspector_dsoinfo_t** out_dso,
                                         backtrace_state** out_bt_state) {
  inspector_dsoinfo_t* dso = inspector_dso_lookup(dso_list_, pc);
  if (dso == nullptr) {
    debugf(1, "No DSO found for pc %p\n", (void*)pc);
    return ZX_ERR_NOT_FOUND;
  }

#if 1  // Skip using libbacktrace until leaks are fixed. ZX-351
  *out_dso = dso;
  *out_bt_state = nullptr;
  return ZX_OK;
#endif

  // If we failed to initialize the cache (OOM) we can still report the
  // DSO we found.
  if (!cache_avail_) {
    *out_dso = dso;
    *out_bt_state = nullptr;
    return ZX_OK;
  }

  const size_t nr_ways = ways_.size();

  for (size_t i = 0; i < nr_ways; ++i) {
    if (ways_[i].dso == dso) {
      debugf(1, "using cached debug info entry for pc %p\n", (void*)pc);
      *out_dso = dso;
      *out_bt_state = ways_[i].bt_state;
      return ZX_OK;
    }
  }

  // PC is in a DSO, but not found in the cache.
  // N.B. From this point on the result is ZX_OK.
  // If there is an "error" the user can still print something (and there's
  // no point in having error messages pollute the backtrace, at least by
  // default).

  *out_dso = dso;
  *out_bt_state = nullptr;

  const char* debug_file = nullptr;
  auto status = inspector_dso_find_debug_file(dso, &debug_file);
  if (status != ZX_OK) {
    // There's no additional debug file available, but we did find the DSO.
    return ZX_OK;
  }

  struct backtrace_state* bt_state =
      backtrace_create_state(debug_file, 0 /*!threaded*/, bt_error_callback, nullptr);
  if (bt_state == nullptr) {
    debugf(1, "backtrace_create_state failed (OOM)\n");
    return ZX_OK;
  }

  // last_used_+1: KISS until there's data warranting something better
  size_t way = (last_used_ + 1) % nr_ways;
  if (ways_[way].dso != nullptr) {
    // Free the entry.
    backtrace_destroy_state(ways_[way].bt_state, bt_error_callback, nullptr);
    ways_[way].dso = nullptr;
    ways_[way].bt_state = nullptr;
  }

  // The iterator doesn't do anything, but we pass |list| anyway
  // in case some day we need it to.
  backtrace_set_so_iterator(bt_state, bt_so_iterator, dso_list_);
  backtrace_set_base_address(bt_state, dso->base);

  ways_[way].dso = dso;
  ways_[way].bt_state = bt_state;
  *out_bt_state = bt_state;
  last_used_ = way;
  return ZX_OK;
}

// Data to pass back from backtrace_pcinfo.
// We don't use libbacktrace to print the backtrace, we only use it to
// obtain file,line#,function_name.

struct bt_pcinfo_data {
  const char* filename;
  int lineno;
  const char* function;
};

// Callback invoked by libbacktrace.

static int btprint_callback(void* vdata, uintptr_t pc, const char* filename, int lineno,
                            const char* function) {
  auto data = reinterpret_cast<bt_pcinfo_data*>(vdata);

  data->filename = filename;
  data->lineno = lineno;
  data->function = function;

  return 0;
}

static void btprint(FILE* f, DebugInfoCache* di_cache, uint32_t n, uintptr_t pc, uintptr_t sp,
                    bool use_new_format) {
  if (use_new_format) {
    fprintf(f, "{{{bt:%u:%#" PRIxPTR ":sp %#" PRIxPTR "}}}\n", n, pc, sp);
    return;
  }

  inspector_dsoinfo_t* dso;
  backtrace_state* bt_state;
  auto status = di_cache->GetDebugInfo(pc, &dso, &bt_state);

  if (status != ZX_OK) {
    // The pc is not in any DSO.
    fprintf(f, "bt#%02u: pc %p sp %p\n", n, (void*)pc, (void*)sp);
    return;
  }

  // Try to use libbacktrace if we can.

  struct bt_pcinfo_data pcinfo_data;
  memset(&pcinfo_data, 0, sizeof(pcinfo_data));

  if (bt_state != nullptr) {
    auto ret = backtrace_pcinfo(bt_state, pc, btprint_callback, bt_error_callback, &pcinfo_data);
    if (ret == 0) {
      // FIXME: How to interpret the result is seriously confusing.
      // There are cases where zero means failure and others where
      // zero means success. For now we just assume that pcinfo_data
      // will only be filled in on success.
    }
  }

  fprintf(f, "bt#%02u: pc %p sp %p (%s,%p)", n, (void*)pc, (void*)sp, dso->name,
          (void*)(pc - dso->base));
  if (pcinfo_data.filename != nullptr && pcinfo_data.lineno > 0) {
    const char* base = path_basename(pcinfo_data.filename);
    // Be paranoid and handle |pcinfo_data.filename| having a trailing /.
    // If so, just print the whole thing and let the user figure it out.
    if (*base == '\0')
      base = pcinfo_data.filename;
    fprintf(f, " %s:%d", base, pcinfo_data.lineno);
  }
  if (pcinfo_data.function != nullptr)
    fprintf(f, " %s", pcinfo_data.function);
  fprintf(f, "\n");
}

static int dso_lookup_for_unw(void* context, unw_word_t pc, unw_word_t* base, const char** name) {
  auto dso_list = reinterpret_cast<inspector_dsoinfo_t*>(context);
  inspector_dsoinfo_t* dso = inspector_dso_lookup(dso_list, pc);
  if (dso == nullptr)
    return 0;
  *base = dso->base;
  *name = dso->name;
  return 1;
}

static void inspector_print_backtrace_impl(FILE* f, zx_handle_t process, zx_handle_t thread,
                                           inspector_dsoinfo_t* dso_list, uintptr_t pc,
                                           uintptr_t sp, uintptr_t fp, bool use_libunwind,
                                           bool use_new_format) {
  // Set up libunwind if requested.

  bool libunwind_ok = use_libunwind;
  if (verbosity_level > 0) {
    // Don't turn on libunwind debugging for -d1.
    // Note: max libunwind debugging level is 16
    unw_set_debug_level(verbosity_level - 1);
  }

  unw_fuchsia_info_t* fuchsia = nullptr;
  unw_addr_space_t remote_as = nullptr;

  if (libunwind_ok) {
    fuchsia = unw_create_fuchsia(process, thread, dso_list, dso_lookup_for_unw);
    if (fuchsia == nullptr) {
      print_error("unw_fuchsia_create failed (OOM)");
      libunwind_ok = false;
    }
  }

  if (libunwind_ok) {
    remote_as = unw_create_addr_space((unw_accessors_t*)&_UFuchsia_accessors, 0);
    if (remote_as == nullptr) {
      print_error("unw_create_addr_space failed (OOM)");
      libunwind_ok = false;
    }
  }

  unw_cursor_t cursor;
  if (libunwind_ok) {
    int ret = unw_init_remote(&cursor, remote_as, fuchsia);
    if (ret < 0) {
      print_error("unw_init_remote failed (%d)", ret);
      libunwind_ok = false;
    }
  }

  if (!libunwind_ok) {
    print_error("Unable to initialize libunwind.");
    print_error("Falling back on heuristics which likely won't work");
    print_error("with optimized code.");
  }

  // TODO: Handle libunwind not finding .eh_frame in which case fallback
  // on using heuristics. Ideally this would be handled on a per-DSO basis.

  // Keep a cache of loaded debug info to maintain some performance
  // without loading debug info for all shared libs.
  // This won't get used if initializing libunwind failed, but we can still
  // use |dso_list|.
  DebugInfoCache di_cache(dso_list, kDebugInfoCacheNumWays);

  // On with the show.

  uint32_t n = 1;
  btprint(f, &di_cache, n++, pc, sp, use_new_format);
  while ((sp >= 0x1000000) && (n < kBacktraceFrameLimit)) {
    if (libunwind_ok) {
      int ret = unw_step(&cursor);
      if (ret < 0) {
        print_error("unw_step failed for pc %p, aborting backtrace here", (void*)pc);
        break;
      }
      if (ret == 0)
        break;
      unw_word_t val;
      unw_get_reg(&cursor, UNW_REG_IP, &val);
      pc = val;
      unw_get_reg(&cursor, UNW_REG_SP, &val);
      sp = val;
    } else {
      sp = fp;
      if (read_mem(process, fp + 8, &pc, sizeof(pc))) {
        break;
      }
      if (read_mem(process, fp, &fp, sizeof(fp))) {
        break;
      }
    }
    btprint(f, &di_cache, n++, pc, sp, use_new_format);
  }

  if (!use_new_format) {
    fprintf(f, "bt#%02d: end\n", n);
  }

  if (n >= kBacktraceFrameLimit) {
    fprintf(f, "warning: backtrace frame limit exceeded; backtrace may be truncated\n");
  }

  unw_destroy_addr_space(remote_as);
  unw_destroy_fuchsia(fuchsia);
}

extern "C" __EXPORT void inspector_print_backtrace_markup(FILE* f, zx_handle_t process,
                                                          zx_handle_t thread,
                                                          inspector_dsoinfo_t* dso_list,
                                                          uintptr_t pc, uintptr_t sp, uintptr_t fp,
                                                          bool use_libunwind) {
  inspector_print_backtrace_impl(f, process, thread, dso_list, pc, sp, fp, use_libunwind, true);
}

extern "C" __EXPORT void inspector_print_backtrace(FILE* f, zx_handle_t process, zx_handle_t thread,
                                                   inspector_dsoinfo_t* dso_list, uintptr_t pc,
                                                   uintptr_t sp, uintptr_t fp, bool use_libunwind) {
  inspector_print_backtrace_impl(f, process, thread, dso_list, pc, sp, fp, use_libunwind, false);
}

}  // namespace inspector
